package com.study.algorithm.binarytree;


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class TreeSort {
    /**
     * 94. 二叉树的中序遍历
     *    1
     *     \
     *      2
     *     /
     *    3
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }

    private void inorder(TreeNode root, List<Integer> res) {
        if (root == null) return;  // 递归终止条件

        inorder(root.left, res);   // 1. 遍历左子树
        res.add(root.val);         // 2. 访问根节点
        inorder(root.right, res);  // 3. 遍历右子树
    }

    /**
     * 94. 二叉树的中序遍历（迭代版本）
     */
    public List<Integer> inorderTraversal1(TreeNode root) {
        // 创建结果容器：用于存储按"左-根-右"顺序遍历得到的节点值
        List<Integer> res = new ArrayList<>();

        // 创建模拟栈：用于替代递归的系统调用栈，存储尚未完成遍历的节点
        Stack<TreeNode> stack = new Stack<>();

        TreeNode curr = root;
        // 循环条件：当前节点不为空 或 栈中还有待处理节点
        while (curr != null || !stack.isEmpty()) {
            // 内循环：一路向左，将路径上的所有节点压入栈中
            while (curr != null) {
                stack.push(curr);    // 保存当前节点，后续需要处理它的右子树
                curr = curr.left;    // 继续向左深入7
            }

            // 弹出栈顶节点（当前最左边的节点）
            curr = stack.pop();
            // 访问节点：将节点值加入结果列表（中序遍历的"根"操作）
            res.add(curr.val);

            // 转向右子树：开始处理当前节点的右子树
            curr = curr.right;
        }

        return res;
    }
}
